
class Solution {
public:
    int superEggDrop(int k, int n) {
        vector<vector<int> > dp(1005, vector<int>(1005));
        for (int i = 0; i < 500; i++)
            dp[1][i] = i;
        for (int i = 2; i < 105; i++) {
            for (int j = 1; j < 500; j++) {
                //if (j == 1) {
                //    dp[i][j] = i;
                //    continue;
                //}
//  1 : 1 2 3 4
//  2 : 1 3 6 10
//  3 : 1 3 9 
                if (j < i) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    
                     if(dp[i][j - 1] + dp[i - 1][j - 1] + 1 > 100000) break;
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + 1;
                }
            }
        }
        int pos = 1;
        while (dp[k][pos] < n) {
            pos++;
        }
        return pos;
    }
};